<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <script>
    /* 
      https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
      思路：https://leetcode-cn.com/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/
      
      dp[i]代表当前元素最大子序和
    */
    let nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];

    function maxSubArray(nums) {
      let max = nums[0]
      let dp = [nums[0]]
      for (let i = 1; i < nums.length; i++) {
        if (dp[i-1] > 0) {
          dp[i] = dp[i-1] + nums[i]
        } else {
          dp[i] = nums[i]
        }
        max = Math.max(max, dp[i])
      }
      return max
    }
    console.log(maxSubArray(nums));
  </script>
</body>
</html>